#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a[100050],n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        if(n%2==1){
            ll ans=0;
            for(int i=2;i<=n-1;i+=2){
                int temp=max(a[i-1],a[i+1]);
                if(a[i]<=temp){
                    ans+=temp-a[i]+1;
                }
            }
            printf("%lld\n",ans);
        }
        else{
            // ll dp[100][2]={0};
            // //dp[2][1]=(max(a[1],a[3])-a[2]+1)>0?(max(a[1],a[3])-a[2]+1):0;
            // for(int i=2;i<=n-1;i++){
            //     if(i%2==0){
            //         dp[i][1]=(max(a[i-1],a[i+1])-a[i]+1)>0?(max(a[i-1],a[i+1])-a[i]+1):0+dp[i-2][1];
            //         dp[i][0]=min(dp[i-1][1],dp[i-2][1]);
            //     }
            //     else{
            //         dp[i][1]=(max(a[i-1],a[i+1])-a[i]+1)>0?(max(a[i-1],a[i+1])-a[i]+1):0+min(dp[i-3][1],dp[i-2][1]);
            //         dp[i][0]=dp[i-1][1];
            //     }
            // }
			ll dp[100050][2]={0};
			for(int i=2;i<n;i++)
			{
				int u=max(a[i-1],a[i+1]);
				if(i%2==0) dp[i][0]=min(dp[i-1][1],dp[i-2][1]);
				else dp[i][0]=dp[i-1][1];
				if(i%2==0) dp[i][1]=max(u-a[i]+1,0)+dp[i-2][1];
				else dp[i][1]=max(u-a[i]+1,0)+min(dp[i-2][1],dp[i-3][1]);
			}            
            printf("%lld\n",dp[n-1][1]<dp[n-1][0]?dp[n-1][1]:dp[n-1][0]);
        }
    }
}